import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */

    //层序遍历非递归的方法，借助辅助队列，能使得它先进先出
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
//二叉树的层序遍历借助辅助栈
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        //如果root===null直接返回
        if(root==null){
            return ans;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        //先把根结点拉入栈
        queue.add(root);
//当栈内不为空时
        while(!queue.isEmpty()){
            //用list保存一层的结点
            ArrayList<Integer> row=new ArrayList<>();
            int n=queue.size();
            //求出栈内的结点数
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                row.add(node.val);

                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            ans.add(row);

        }
        return ans;
    }
}